FJSC2020 合集

这是个天坑，咕咕咕（2020.8.12~）。

文风借鉴 抄袭 Dreamunk 的 FJWC2020 题解合集。

这么快就 2020 了，回想我第一次参加省夏是初一的事（虽然那时参加的是普及组的）。

今年参加了 FJOI，直接就爆零了，唉。。。

今年参加中考了，全机房就我 whk 最差了 T_T。

今年我就要成为高中生了，在创新班会被踩的呀。

省夏因为参加国冬没去上课，现在一时兴起，想写写省夏的题解。

学习兔巨神和 Yuc 巨神，红的是主要看题解的，绿的是主要自己想的。（安慰自己，我这么菜，看题解是正常的，是正常的……）

Day1

T1 num

简要题意：求区间 $[l,r]$ 中有多少个整数都能是它所有非 $0$ 数位的倍数，数据组数为 $T$。$1\le T\le 10,1\le l\le r\le 10^{18}$。

数位 DP。因为 $\operatorname{lcm}(1,2,3,\cdots,9)=2520$，所以只需要考虑这个数在模 $2520$ 意义下的值即可。设 $f_{i,j,k,1/0}$ 表示填到第 $i$ 位，模意义下的值为 $j$，当前所有非零位的 $\operatorname{lcm}$ 为 $k$，是否碰到当前位上界的方案数，转移显然为：

$f_{i,j,k,o}=\sum\limits_{p=0}^{mx}{f_{i-1,(10j+p)\bmod{2520},\operatorname{lcm}(k,p),o\land p=mx}}$

其中 $mx=\begin{cases}dig_i & o=1 \\ 9 & o=0 \end{cases}$。

这时又有问题，$20\times 2520\times 2520$ 的时空复杂度有点大，这时我们发现 $\operatorname{lcm}$ 的取值不到 $100$ 种左右，我们可以随便拿一个 $map$ 啥的来维护。

Code：

#include <stdio.h>
#include <string.h>
#define il inline
#define int long long
using namespace std;
const int P=2520;

int tt,d[19],L,mp[P+1],f[20][P][49];

il int gcd(int a,int b){return b?gcd(b,a%b):a;}

il int lcm(int a,int b){return a*b/gcd(a,b);}

il int dp(int p,int s,int c,int o)
{
    if (!p) return s%c==0;
    if (!o&&~f[p][s][mp[c]]) return f[p][s][mp[c]];
    int i,k=o?d[p]:9,res=0;
    for (i=0; i<=k; i++) res+=dp(p-1,(s*10+i)%P,lcm(c,i?i:1),o&&i==k);
    if (!o) f[p][s][mp[c]]=res;
    return res;
}

il int cal(int x)
{
    for (L=0; x; x/=10) d[++L]=x%10;
    return dp(L,0,1,1);
}

signed main()
{
    freopen("num.in","r",stdin),freopen("num.out","w",stdout);
	
    scanf("%lld",&tt),memset(f,-1,sizeof f); int l,r;
    for (l=1,r=0; l<=P; l++) if (P%l==0) mp[l]=++r;
	
    while (tt--) scanf("%lld%lld",&l,&r),printf("%lld\n",cal(r)-cal(l-1));
	
    return 0;
}

Day2

T1 river

简要题意：给定一个长度为 $m$ 的序列 $\{a_i\}$，现在是第 $0$ 天，你要从 $0$ 走到 $n$。如果现在是第 $i$ 天，你在位置 $j$，你可以花费 $a_{i\bmod m}$ 天走到位置 $j+1$，或者等待一天。$n\leq10^9,m\leq10^6,0\le a_i<m$。

我们设 $g_i$ 表示目前第 $i$ 天时到达下一个位置需要花费的最小天数。这个东西非常好求，我们只需要将数组翻倍，然后就有：

$g_i=\max\{a_i,g_{i+1}+1\}$

求出了 $g_i$ 我们就可以 DP 了。肯定越早到越好，因为早到可以有更多选择。我们设 $f_i$ 表示移动到位置 $i$ 需要的最小时间，那么显然有方程：

$f_{i+1}=f_i+g_{f_i \bmod m}$

这个方程式显然是有循环节的，我们找到这个循环节就好了。

求 $g_i$ 和找循环节的过程都是 $O(m)$ 的，所以时空复杂度均为 $O(m)$。

Code：

#include <bits/stdc++.h>
#define ll long long
const int N=2e6+5;

int n,m,a[N],b[N],c[N]; ll ans,f[N];

int main()
{
    freopen("river.in","r",stdin),freopen("river.out","w",stdout);

    scanf("%d%d",&m,&n); int i,x=0;
    for (i=0; i<n; i++) scanf("%d",a+i),a[i+n]=a[i];
    for (i=n+n-1; ~i; i--) a[i]=std::min(a[i],a[i+1]+1);

    for (i=1; i<=m; i++,ans+=a[x],x=(x+a[x])%n)
    {
        if (b[x]) return printf("%lld",f[c[b[x]+(m-b[x]+1)%(i-b[x])]]+(m-b[x]+1)/(i-b[x])*(ans-f[x])),0;
        f[x]=ans,c[b[x]=i]=x;
    }

    return 0;
}

T2 tree

简要题意：有一颗大小为 $N$ 的树，树上每条边有一个数字，有 $M$ 次询问，每次询问一对 $(x,y)$，你需要回答从 $x$ 到 $y$ 的路径的数字任意排列是否能构成一个回文的序列。每次询问的 $(x,y)$ 是通过某种方式生成的，最后输出回答 Yes 的个数和。$N\leq5\times10^6,M\leq2\times10^7$。

只有至多一个字符个数为奇数时才能构成回文串，那么个数为偶数的字符就没有影响，那么考虑运用位运算异或的性质，将个数为偶数的消除掉。我们给每种边权随机赋权，然后预处理出 $S_i$，$S_v=S_u\ xor\ w(u,v)(v\in son_u)$。那么判断两个点 $x,y$ 是否可以就是判断 $S_x\ xor\ S_y$ 是否为 $0$ 或者是否为一种边权的权值。哈希赋权要好一点，不然会被卡。时间复杂度为 $O(n+m)$，空间复杂度为 $O(n)$。

Code：

#include <stdio.h>
#include <unordered_map>
#define il inline
#define int long long
using namespace std;
const int N=5e6+5; unsigned int rn=233;

int n,m,ans,val[N];
int to[N+N],nx[N+N],wt[N+N],hd[N],sze;
unordered_map<int,int> o1,o2;

il int Rand(){rn=rn>>5^rn,rn=rn<<17^rn,rn=rn>>9^rn,rn>>=1;return rn;}

il char gc()
{
    static char buf[1<<20],*ss,*tt;
    if (tt==ss)
    {
        tt=(ss=buf)+fread(buf,1,1<<20,stdin);
        if (tt==ss) return EOF;
    }
    return *ss++;
}

il int read()
{
    int res; char c;
    while ((c=gc())<'0'||c>'9'); res=c^48;
    while ((c=gc())>='0'&&c<='9') res=(res<<3)+(res<<1)+(c^48);
    return res;
}

il void add(int u,int v,int w){to[++sze]=v,nx[sze]=hd[u],wt[sze]=w,hd[u]=sze;}

il int get(int v)
{
    if (!o1[v]) o2[o1[v]=Rand()]=v;
    return o1[v];
}

il void dfs(int u,int F)
{
    int i,v;
    for (i=hd[u]; i; i=nx[i]) if ((v=to[i])!=F) val[v]=val[u]^get(wt[i]),dfs(v,u);
}

il int check(int v){return !v||o2.count(v);}

signed main()
{
    freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
    
    n=read(),m=read(); int i,u,v,w;
    for (i=1; i<n; i++) u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);
    dfs(1,0);
    
    for (u=read(),v=read(); m; m--)
    {
        if (check(val[u%n+1]^val[v%n+1])) ans++;
        u=666073ll*u%1000000007ll,v=233ll*v%998244353ll;
    }
    printf("%lld",ans);
	
    return 0;
}

Day3

T1 rps

简要题意：有 $2^n$ 个人参加了猜拳游戏。游戏共 $n$ 轮，第一轮第 $1$ 位选手和第 $2$ 位选手对战，胜者为新的第 $1$ 位选手，第 $3$ 位选手和第 $4$ 位选手对战，胜者为新的第 $2$ 位选手，以此类推。每个选手都有一个偏爱手势，比赛时只会使用该手势。当两个人偏爱手势相同时游戏无法结束。现在知道每种偏爱手势的人数，安排初始次序使得游戏能够结束。$R+P+S=2^n,1\leq n\leq 20$，其中 $R,P,S$ 分别表示偏好手势为石头、布、剪刀的人数。

发现只要确定了最后胜利的是谁，整个局势就可以被确定，所以枚举胜利的是哪一个，然后确定局势完判断这个局势是否满足要求即可。字典序问题可以用 string 解决。时间复杂度是 $O(2^nn)$，空间复杂度是 $O(2^n)$。

Code：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define il inline
using namespace std;

int n,r,p,s; string ans;

il string dfs(int c,int x)
{
    if (!c) return string{x};
    string a=dfs(c-1,x),b=dfs(c-1,x%3+1);
    if (a<b) return a+b;
    return b+a;
}

il int check()
{
    int o[4]={0,p,r,s};
    for (auto c:ans) if (--o[c]<0) return 0;
    return 1;
}

int main()
{
    freopen("rps.in","r",stdin),freopen("rps.out","w",stdout);
	
    scanf("%d%d%d",&r,&p,&s); int i;
    for (i=1; i<21; i++) if (r+p+s==1<<i) n=i;
	
    for (i=1; i<4; i++) if (ans=dfs(n,i),check())
    {
        for (auto c:ans)
        {
            if (c==1) putchar('P');
            if (c==2) putchar('R');
            if (c==3) putchar('S');
        }
        return 0;
    }
    puts("IMPOSSIBLE");
	
    return 0;
}

T2 vote

简要题意：有 $n$ 个人参加了投票游戏。每个人会投支持票或者反对票，第 $i$ 个人投支持票的概率是 $p_i$。选出 $k$ 个人使平票的概率最大。$2\leq n\leq2000，2\leq k\leq n,2\mid k,\forall 1\leq i\leq n,0\leq p_i\leq1$。

关键的一步我没有想到：将 $p_i$ 从小到大排好序，则存在一个最优方案，其中选择的同学是一段前缀和一段后缀。

证明：
我们假设存在一个位置 $i$，它前后都没有被选中。那么我们固定除了 $i$ 之外的所有已经被选择的位置，并设还差一个支持票的概率为 $x$，还差一个反对票的概率为 $y$。
那么平票的概率就是 $p_ix+(1-p_i)y=(x-y)p_i+y$，这是一个一次函数关系，那么不是两端点的 $i$ 就肯定没有去两端点来得优，所以矛盾。
故原命题成立。
[证毕]

知道了这个性质后就简单了，我们 $O(n^2)$ 求出 $f_{i,j},g_{i,j}$，分别表示前/后 $i$ 个中有 $j$ 个投支持票的概率。然后随便计算一下答案就好了。时空复杂度均为 $O(n^2)$。

Code：

#include <stdio.h>
#include <algorithm>
#define db double
using namespace std;
const int N=2005;

int n,k; db ans,p[N],f[N][N],g[N][N];

int main()
{
    freopen("vote.in","r",stdin),freopen("vote.out","w",stdout);
	
    scanf("%d%d",&n,&k); int i,j,l; db res;
    for (i=1; i<=n; i++) scanf("%lf",p+i);
    sort(p+1,p+n+1);
	
    for (i=f[0][0]=g[n+1][0]=1; i<=n; i++)
    {
        for (j=n; j; j--) f[i][j]=p[i]*f[i-1][j-1]+(1-p[i])*f[i-1][j];
        f[i][0]=(1-p[i])*f[i-1][0];
    }
    for (i=n; i; i--)
    {
        for (j=n; j; j--) g[i][j]=p[i]*g[i+1][j-1]+(1-p[i])*g[i+1][j];
        g[i][0]=(1-p[i])*g[i+1][0];
    }
    for (i=0; i<=k; i++)
    {
        j=n+1+i-k,res=0;
        for (l=0; l+l<=k; l++) res+=f[i][l]*g[j][k/2-l];
        ans=max(ans,res);
    }
    printf("%.10lf",ans);
	
    return 0;
}

Day4

T1 mahjong

这是之前校内模拟赛的赛题 （学长好懒）。

简要题意：给 $T$ 副有 $13$ 或者 $14$ 张牌的麻将，$14$ 张判断是否可以胡，$13$ 张判断哪些是停牌，规则同传统麻将。

直接模拟，判断胡牌就先凑凤头，再来刻子，最后顺子；找听牌则直接将每一张加进去然后判断即可。要注意若一张牌已经抽到四张了那么不能加这张牌。

Code：

#include <stdio.h>
#define il inline
using namespace std;

int tt,n; char s[3];
int tuc[50],tuf[50];

il int id()
{
    if (s[1]=='m') return 0+s[0]-'0';
    if (s[1]=='p') return 11+s[0]-'0';
    if (s[1]=='s') return 22+s[0]-'0';
}

il int check()
{
    int i,j,o;
    for (i=1; i<32; i++)
        if (tuc[i]>1)
        {
            for (j=1,tuc[i]-=2,o=1; j<34; j++) tuf[j]=tuc[j];
            for (j=1; j<34; j++)
            {
                if (tuf[j]<0){o=0;break;} 
                tuf[j]%=3,tuf[j+1]-=tuf[j],tuf[j+2]-=tuf[j];
            }
            tuc[i]+=2;
            if (o) return 1;
        }
    return 0;
}

int main()
{
    freopen("mj.in","r",stdin),freopen("mj.out","w",stdout);
	
    scanf("%d%d",&n,&tt); int i;
    while (tt--)
    {
    	for (i=1; i<34; i++) tuc[i]=0;
    	for (i=1; i<=n; i++) scanf("%s",s),tuc[id()]++;
    	if (n==14) printf("%d\n",check());
    	else
    	{
    	    for (i=1; i<10; i++)
                if (tuc[i]<4)
                {
                    tuc[i]++;
                    if (check()) printf("%dm ",i);
                    tuc[i]--;
                }
            for (i=12; i<21; i++)
                if (tuc[i]<4)
                {
                    tuc[i]++;
                    if (check()) printf("%dp ",i-11);
                    tuc[i]--;
                }
            for (i=23; i<32; i++)
                if (tuc[i]<4)
                {
                    tuc[i]++;
                    if (check()) printf("%ds ",i-22);
                    tuc[i]--;
                }
		    puts("");
		}
	}
	
    return 0;
}

T2 tree

简要题意：给你一棵有 $N$ 个节点的有根树，根节点编号为 $1$，树上每一个节点有一个权值，你需要维护这棵树进行描述如下的 $M$ 次操作：

• 1 u v: 将点 $u$ 的权值加上 $v$。
• 2 a b v：将覆盖 $a,b$ 的点数最少的子树的所有点的权值加上 $v$。
• 3 a b: 查询覆盖 $a,b$ 的点数最少的子树的根节点编号 $id$ 及权值 $val_{id}$。
• 4 u：查询以节点 $u$ 为根的子树的节点权值之和 $sum_u$。
  由于权值可能很大，所有的查询结果都请对 $10^9+7$ 取模。

覆盖 $a,b$ 的点数最少的子树的根显然就是 $LCA(a,b)$，剩下的操作用树剖、$dfs$ 序都可以实现，本人用的是树剖求 $LCA$ 加线段树实现区间操作，复杂度为 $O(m\log{n})$，空间复杂度为 $O(n)$。

Code：

#include <stdio.h>
#include <algorithm>
#define il inline
using namespace std;
const int N=5e5+1,P=1e9+7;

int n,m,tot,fa[N],val[N],dep[N];
int to[N],nx[N],head[N],sze;
int sz[N],son[N],top[N],dfn[N],rev[N];
int t[4*N],lz[4*N];

il void build(int p,int l,int r)
{
    if (l==r){t[p]=val[rev[l]]%P;return;} int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r),t[p]=(t[p<<1]+t[p<<1|1])%P;
}

il void tg(int p,int l,int r,int v){lz[p]=(lz[p]+v)%P,t[p]=(t[p]+1ll*(r-l+1)*v%P)%P;}

il void pushdown(int p,int l,int r,int mid){if (lz[p]) tg(p<<1,l,mid,lz[p]),tg(p<<1|1,mid+1,r,lz[p]),lz[p]=0;}

il void uptqj(int p,int l,int r,int x,int y,int v)
{
    if (l>=x&&r<=y) return tg(p,l,r,v); 
    int mid=l+r>>1; pushdown(p,l,r,mid);
    if (x<=mid) uptqj(p<<1,l,mid,x,y,v);
    if (y>mid) uptqj(p<<1|1,mid+1,r,x,y,v);
    t[p]=(t[p<<1]+t[p<<1|1])%P;
}

il int query(int p,int l,int r,int x,int y)
{
    if (l>=x&&r<=y) return t[p];
    int mid=l+r>>1,res=0; pushdown(p,l,r,mid);
    if (x<=mid) res=(res+query(p<<1,l,mid,x,y))%P;
    if (y>mid) res=(res+query(p<<1|1,mid+1,r,x,y))%P;
    return res;
}

il void add(int u,int v){to[++sze]=v,nx[sze]=head[u],head[u]=sze;}

il int LCA(int x,int y)
{
    for ( ; top[x]!=top[y]; x=fa[top[x]]) if (dep[top[x]]<dep[top[y]]) swap(x,y);
    return dep[x]<dep[y]?x:y;
}

il void dfs1(int u,int F)
{
    dep[u]=dep[F]+1,sz[u]=1; int i,v;
    for (i=head[u]; i; i=nx[i])
    {
        v=to[i],dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[son[u]]) son[u]=v;
    }
}

il void dfs2(int u,int t)
{
    top[u]=t,dfn[u]=++tot,rev[tot]=u; int i,v;
    if (son[u]) dfs2(son[u],t);
    for (i=head[u]; i; i=nx[i]) if (!top[v=to[i]]) dfs2(v,v);
}

int main()
{
    freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
	
    scanf("%d%d",&n,&m); int i,x,y,v,l;
    for (i=2; i<=n; i++) scanf("%d",fa+i),add(fa[i],i);	
    for (i=1; i<=n; i++) scanf("%d",val+i);
    dfs1(1,0),dfs2(1,1),build(1,1,n);
	
    while (m--)
    {
        scanf("%d%d",&i,&x);
        if (i==1) scanf("%d",&v),uptqj(1,1,n,dfn[x],dfn[x],v);
        if (i==2) scanf("%d%d",&y,&v),l=LCA(x,y),uptqj(1,1,n,dfn[l],dfn[l]+sz[l]-1,v);
        if (i==3) scanf("%d",&y),l=LCA(x,y),printf("%d %d\n",l,query(1,1,n,dfn[l],dfn[l]));
        if (i==4) printf("%d\n",query(1,1,n,dfn[x],dfn[x]+sz[x]-1));
    }
	
    return 0;
}

T3 permutation

简要题意：对于这个排列 $P$，给一个定义：一个区间 $[L,R]$ 被称为「美丽的」，当且仅当 $P$ 的这个区间是元素连续的区间。也就是说，如果区间 $[L,R]$ 满足该区间内元素升序排序之后是一个公差为 $1$ 的等差数列。现在有 $M$ 个区间 $[l_i,r_i]$，求包含这个区间的最小的「美丽的」区间 $[L_i,R_i]$。$N,M\le 10^5$。

这是之前校内模拟赛的赛题 （学长好懒）。

我们考虑位置 $i,i+1$，它们的值分别为 $val_i,val_{i+1}$。如果 $i,i+1$ 这两个位置可以出现在一段“美丽的”区间中，那么，由“美丽的”区间的定义，$[val_i,val_{i+1}]$ 内的所有值，都需要在区间中出现。即，令 $L,R$ 为 $[val_i,val_{i+1}]$ 内的所有值出现位置的左右端点，$[L,R]$ 都要在区间中出现。

那么我们求出所有的 $i,i+1$ 对应的 $[L_i,R_i]$，询问 $[x,y]$ 的答案就是区间内每个范围的。

$L_i,R_i$ 可以用 ST 表求出，询问时可以再建两个关于 $L_i,R_i$ 的 ST 表，做到 $O(1)$ 询问。

求出 $L_i,R_i$ 后，剩下的就和 此题 一样了。

最暴力的方法就是将 $i$ 向 $[L_i,R_i]$ 中的所有点全部连有向边，然后在图上 Tarjan 缩点后直接拓扑排序后缀和。但是这样边数为 $O(n^2)$ 级别的，无法通过本题。

我们有两种方法优化建图：

法一

观察连边的过程，每个点连边的点集一定是数轴上的一个区间，与是我们考虑对于连边的过程进行优化。

建一棵线段树，对于一个表示区间 $[l,r]$ 的点，从这个点向表示区间 $[l,mid]$ 和区间 $[mid+1,r]$ 的两个点连有向边。

对于原图中的边 $[i,j],j\in[l,r]$，将这条边从 $i$ 连向表示 $[l,r]$ 的若干个点即可。

法二

可以发现，我们要求出的是在 $i$ 左边找到离 $i$ 最近的且能覆盖到 $i$的点 $j$。

我们可以从左往右维护一个单调栈，设栈顶的点编号为 $t$，当前要求的点为 $i$。如果 $R[t]<i$ ，即第 $t$ 个点覆盖不到 $i$，就弹出栈顶元素，直到栈空或栈顶合法为止。将 $i$ 弹入时，若 $R[t]<R[i]$，显然可以将栈顶弹出，最后再将 $i$ 点扔到栈里。右边的同理。

由于 ST 表的存在，所以两种方法的时空复杂度均为 $O(n\log{n})$。

据说还有纯用线段树的神仙做法，但是本彩笔不会。

Code：

#include <stdio.h>
#include <algorithm>
#include <vector>
#define il inline
#define pb push_back
using namespace std;
const int N=1e5+1;

int n,m,a[N],b[N],L[N],R[N];
int f[2][N][17],lg[N];
int t,s[N],ok[N],bel[N];
vector<int> g1[N],g2[N];

il void dfs1(int u)
{
    ok[u]=1;
    for (auto v:g1[u]) if (!ok[v]) dfs1(v);
    s[++t]=u;
}

il void dfs2(int u,int c)
{
    bel[u]=c,L[c]=min(L[c],u),R[c]=max(R[c],u);
    for (auto v:g2[u]) if (!bel[v]) dfs2(v,c);
}

il void init(int t,int *y)
{
    int i,j;
    for (i=1; i<=n; i++) f[t][i][0]=y[i];
    for (j=1; j<17; j++) for (i=1; i+(1<<j)-1<=n; i++)
    {
        if (t&1) f[t][i][j]=max(f[t][i][j-1],f[t][i+(1<<j-1)][j-1]);
        else f[t][i][j]=min(f[t][i][j-1],f[t][i+(1<<j-1)][j-1]);
    }
}

il int query(int t,int l,int r)
{
    int s=lg[r-l+1];
    if (t&1) return max(f[t][l][s],f[t][r-(1<<s)+1][s]);
    return min(f[t][l][s],f[t][r-(1<<s)+1][s]);
}

int main()
{
    freopen("permutation.in","r",stdin),freopen("permutation.out","w",stdout);

    scanf("%d",&n); int i,x,y;
    for (i=1,lg[0]=-1; i<=n; i++) scanf("%d",a+i),b[a[i]]=i,lg[i]=lg[i>>1]+1;
    init(0,b),init(1,b);
    for (i=1; i<n; i++)
	x=min(a[i],a[i+1]),y=max(a[i],a[i+1]),
	L[i]=query(0,x,y),R[i]=query(1,x,y)-1;
	
    for (i=1; i<n; i++)
    {
        while (t&&R[s[t]]<i) t--;
        if (t) g1[s[t]].pb(i),g2[i].pb(s[t]);
        s[++t]=i;
    }
    for (i=n-2; i; i--)
    {
        while (t&&L[s[t]]>i) t--;
        if (t) g1[s[t]].pb(i),g2[i].pb(s[t]);
        s[++t]=i;
    }
    for (i=1; i<n; i++) L[i]=1e9,R[i]=0;
    for (i=1,t=0; i<n; i++) if (!ok[i]) dfs1(i);
    for (i=t; i; i--) if (!bel[s[i]]) dfs2(s[i],s[i]);
    for (i=1; i<n; i++) for (auto j:g1[s[i]])
        if (bel[s[i]]!=bel[j]) L[bel[s[i]]]=min(L[bel[s[i]]],L[bel[j]]),R[bel[s[i]]]=max(R[bel[s[i]]],R[bel[j]]);
    for (i=1; i<n; i++) L[i]=L[bel[i]],R[i]=R[bel[i]];
	
    init(0,L),init(1,R);
    for (scanf("%d",&m); m; m--)
    {
        scanf("%d%d",&x,&y);
        if (x==y) printf("%d %d\n",x,y);
        else y--,printf("%d %d\n",query(0,x,y),query(1,x,y)+1);
    }
	
    return 0;
}

Day5

Day6

T1 cube

简要题意：给一个魔方的原始样子，再给出操作序列，输出操作过后的魔方。保证魔方是个标准六面魔方，且能够进行复原，字符串长度小于等于 $10000$。

大模拟题，直接暴力模拟 $18$ 种旋法或者平面展开后操作，本人选择前者。

#include <stdio.h>
#include <string.h>
#define il inline
#define foR(i) for (int i=1; i<4; i++)
#define For(i,j) for (int i=1; i<4; i++) for (int j=1; j<4; j++)
using namespace std;

int a[4][4],b[4][4],c[4][4],d[4][4],e[4][4],f[4][4],w[4][4]; char q[10001];

il void _a()
{
    For(i,j) w[i][j]=b[i][j];
    For(i,j) b[i][j]=w[j][4-i];
    foR(i) w[i][1]=a[i][1];
    foR(i) a[i][1]=c[i][1];
    foR(i) c[i][1]=e[i][1];
    foR(i) e[i][1]=f[i][1];
    foR(i) f[i][1]=w[i][1];
}

il void _A()
{
    For(i,j) w[i][j]=b[i][j];
    For(i,j) b[i][j]=w[4-j][i];
    foR(i) w[i][1]=f[i][1];
    foR(i) f[i][1]=e[i][1];
    foR(i) e[i][1]=c[i][1];
    foR(i) c[i][1]=a[i][1];
    foR(i) a[i][1]=w[i][1];
}

il void _b()
{
    foR(i) w[i][2]=a[i][2];
    foR(i) a[i][2]=c[i][2];
    foR(i) c[i][2]=e[i][2];
    foR(i) e[i][2]=f[i][2];
    foR(i) f[i][2]=w[i][2];
}

il void _B()
{
    foR(i) w[i][2]=f[i][2];
    foR(i) f[i][2]=e[i][2];
    foR(i) e[i][2]=c[i][2];
    foR(i) c[i][2]=a[i][2];
    foR(i) a[i][2]=w[i][2];
}

il void _c()
{
    For(i,j) w[i][j]=d[i][j];
    For(i,j) d[i][j]=w[4-j][i];
    foR(i) w[i][3]=a[i][3];
    foR(i) a[i][3]=c[i][3];
    foR(i) c[i][3]=e[i][3];
    foR(i) e[i][3]=f[i][3];
    foR(i) f[i][3]=w[i][3];
}

il void _C()
{
    For(i,j) w[i][j]=d[i][j];
    For(i,j) d[i][j]=w[j][4-i];
    foR(i) w[i][3]=f[i][3];
    foR(i) f[i][3]=e[i][3];
    foR(i) e[i][3]=c[i][3];
    foR(i) c[i][3]=a[i][3];
    foR(i) a[i][3]=w[i][3];
}

il void _d()
{
    For(i,j) w[i][j]=c[i][j];
    For(i,j) c[i][j]=w[j][4-i];
    foR(i) w[i][1]=d[i][1];
    foR(i) d[i][1]=e[1][4-i];
    foR(i) e[1][i]=b[i][3];
    foR(i) b[i][3]=a[3][4-i];
    foR(i) a[3][i]=w[i][1];
}

il void _D()
{
    For(i,j) w[i][j]=c[i][j];
    For(i,j) c[i][j]=w[4-j][i];
    foR(i) w[3][i]=a[3][i];
    foR(i) a[3][i]=b[4-i][3];
    foR(i) b[i][3]=e[1][i];
    foR(i) e[1][i]=d[4-i][1];
    foR(i) d[i][1]=w[3][i];
}

il void _e()
{
    foR(i) w[i][2]=d[i][2];
    foR(i) d[i][2]=e[2][4-i];
    foR(i) e[2][i]=b[i][2];
    foR(i) b[i][2]=a[2][4-i];
    foR(i) a[2][i]=w[i][2];
}

il void _E()
{
    foR(i) w[2][i]=a[2][i];
    foR(i) a[2][i]=b[4-i][2];
    foR(i) b[i][2]=e[2][i];
    foR(i) e[2][i]=d[4-i][2];
    foR(i) d[i][2]=w[2][i];
}

il void _f()
{
    For(i,j) w[i][j]=f[i][j];
    For(i,j) f[i][j]=w[4-j][i];
    foR(i) w[1][i]=a[1][i];
    foR(i) a[1][i]=d[i][3];
    foR(i) d[i][3]=e[3][4-i];
    foR(i) e[3][i]=b[i][1];
    foR(i) b[i][1]=w[1][4-i];
}

il void _F()
{
    For(i,j) w[i][j]=f[i][j];
    For(i,j) f[i][j]=w[j][4-i];
    foR(i) w[1][i]=a[1][i];
    foR(i) a[1][i]=b[4-i][1];
    foR(i) b[i][1]=e[3][i];
    foR(i) e[3][i]=d[4-i][3];
    foR(i) d[i][3]=w[1][i];
}

il void _h()
{
    For(i,j) w[i][j]=a[i][j];
    For(i,j) a[i][j]=w[j][4-i];
    foR(i) w[1][i]=c[1][i];
    foR(i) c[1][i]=b[1][i];
    foR(i) b[1][i]=f[3][4-i];
    foR(i) f[3][i]=d[1][4-i];
    foR(i) d[1][i]=w[1][i];
}

il void _H()
{
    For(i,j) w[i][j]=a[i][j];
    For(i,j) a[i][j]=w[4-j][i];
    foR(i) w[1][i]=c[1][i];
    foR(i) c[1][i]=d[1][i];
    foR(i) d[1][i]=f[3][4-i];
    foR(i) f[3][i]=b[1][4-i];
    foR(i) b[1][i]=w[1][i];
}

il void _i()
{
    foR(i) w[2][i]=c[2][i];
    foR(i) c[2][i]=b[2][i];
    foR(i) b[2][i]=f[2][4-i];
    foR(i) f[2][i]=d[2][4-i];
    foR(i) d[2][i]=w[2][i];
}

il void _I()
{
    foR(i) w[2][i]=c[2][i];
    foR(i) c[2][i]=d[2][i];
    foR(i) d[2][i]=f[2][4-i];
    foR(i) f[2][i]=b[2][4-i];
    foR(i) b[2][i]=w[2][i];
}

il void _j()
{
    For(i,j) w[i][j]=e[i][j];
    For(i,j) e[i][j]=w[4-j][i];
    foR(i) w[3][i]=c[3][i];
    foR(i) c[3][i]=b[3][i];
    foR(i) b[3][i]=f[1][4-i];
    foR(i) f[1][i]=d[3][4-i];
    foR(i) d[3][i]=w[3][i];
}

il void _J()
{
    For(i,j) w[i][j]=e[i][j];
    For(i,j) e[i][j]=w[j][4-i];
    foR(i) w[3][i]=c[3][i];
    foR(i) c[3][i]=d[3][i];
    foR(i) d[3][i]=f[1][4-i];
    foR(i) f[1][i]=b[3][4-i];
    foR(i) b[3][i]=w[3][i];
}

int main()
{
    freopen("cube.in","r",stdin),freopen("cube.out","w",stdout);
	
    int k,l;
    For(i,j) scanf("%d",a[i]+j);
    for (k=1; k<4; k++)
    {
        foR(i) scanf("%d",b[k]+i);
        foR(i) scanf("%d",c[k]+i);
        foR(i) scanf("%d",d[k]+i);
    }
    For(i,j) scanf("%d",e[i]+j);
    For(i,j) scanf("%d",f[i]+j);
    scanf("%s",q),l=strlen(q);
	
    for (int i=0; i<l; i++)
    {
	if (q[i]=='a') _a();
	if (q[i]=='A') _A();
	if (q[i]=='b') _b();
	if (q[i]=='B') _B();
	if (q[i]=='c') _c();
	if (q[i]=='C') _C();
	if (q[i]=='d') _d();
	if (q[i]=='D') _D();
	if (q[i]=='e') _e();
	if (q[i]=='E') _E();
	if (q[i]=='f') _f();
	if (q[i]=='F') _F();
	if (q[i]=='h') _h();
	if (q[i]=='H') _H();
	if (q[i]=='i') _i();
	if (q[i]=='I') _I();
	if (q[i]=='j') _j();
	if (q[i]=='J') _J();
    }
    For(i,j) printf("%d%c",a[i][j]," \n"[j==3]);
    for (k=1; k<4; k++)
    {
        foR(i) printf("%d ",b[k][i]);
        foR(i) printf("%d ",c[k][i]);
        foR(i) printf("%d ",d[k][i]);
        puts("");
    }
    For(i,j) printf("%d%c",e[i][j]," \n"[j==3]);
    For(i,j) printf("%d%c",f[i][j]," \n"[j==3]);

    return 0;
}

T2 tree

简要题意：有一颗 $n$ 个点的树，又有 $m$ 条加边，第 $i$ 条加边连接 $u_i,v_i$ 两个点。求有多少种方案，要求割掉一条原树中的边和一条加边，使得原图不连通。$1\le n,m\le 3\times 10^5$。

本题为四校原题~~(说明省夏今天的出题人懒）~~，以下树边均指原树中的边。

显然加边 $(x,y)$ 相当于给树边简单路径 $(x,y)$ 加上了保险，覆盖了一遍这条路径。

考虑如果切断一条树边，要怎样选择加边，使得原图不联通。分三类情况讨论：

• 这条边只被一个路径覆盖，则切断了这条边，只有把对应路径的加边切断才可以。
• 这条边没有被任何一个路径覆盖，那么只要切断了这条边，原图就已经不联通了，剩下的 $m$ 条加边切断那一条都可以。
• 这条边只被不止一个路径覆盖，则切断了这条边，不管选择那一条加边都无法使原图不联通。

那么我们只需要统计每条边被多少个路径覆盖即可，这直接树上差分解决，时空复杂度均为 $O(n)$ 或 $O(n\log{n})$ （取决于求 $LCA$ 的方式）。

Code：

#include <stdio.h>
#include <algorithm>
#define il inline
using namespace std;
const int N=3e5+5;

int n,m,dep[N],fa[N][21],val[N]; long long ans;
int to[N+N],nx[N+N],hd[N],sze;

il void add(int u,int v){to[++sze]=v,nx[sze]=hd[u],hd[u]=sze;}

il int LCA(int x,int y)
{
    if (dep[x]<dep[y]) swap(x,y); int i; 
    for (i=20; ~i; i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if (x==y) return x;
    for (i=20; ~i; i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

il void init(int u,int F)
{
    dep[u]=dep[F]+1; int i,v;
    for (i=0; i<20; i++) fa[u][i+1]=fa[fa[u][i]][i];
    for (i=hd[u]; i; i=nx[i]) if ((v=to[i])!=F) init(v,fa[v][0]=u);
}

il void dfs(int u,int F){for (int i=hd[u],v; i; i=nx[i]) if ((v=to[i])!=F) dfs(v,u),val[u]+=val[v];}

int main()
{
    freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
	
    scanf("%d%d",&n,&m); int i,u,v;
    for (i=1; i<n; i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    init(1,0);
	
    for (i=1; i<=m; i++) scanf("%d%d",&u,&v),val[u]++,val[v]++,val[LCA(u,v)]-=2;
    for (dfs(1,0),i=2; i<=n; i++)
    {
        if (val[i]==0) ans+=1ll*m;
        if (val[i]==1) ans++;
    }
    printf("%lld",ans);
	
    return 0;
} 

T3 missile

简要题意：三维导弹拦截。$1\leq n\leq1000$。所有数字均不超过 $10^6$。

第一个问题直接 $O(n^2)$ DP 即可。

第二个问题：若打完 $a$ 可以打 $b$，则 $a$ 向 $b$ 连一条有向边，那么答案就是这个 DAG 的最小路径覆盖，直接 $dinic$ 或者别的算法解决，复杂度为 $O(\sqrt{N}M)$，其中 $N,M$ 分别为网络流图的点数与边数。

Code：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define il inline
using namespace std;
const int N=2005,M=N*N;

int n,ans,S,T,f[N],lev[N],it[N],q[M],h,t;
int to[M],nx[M],cap[M],head[N],sze=1;
struct node{int x,y,z;}p[N];

il bool cmp(node a,node b){return a.x<b.x;}

il void add(int u,int v,int c){to[++sze]=v,nx[sze]=head[u],cap[sze]=c,head[u]=sze;}

il void ins(int u,int v,int c){add(u,v,c),add(v,u,0);}

il int bfs()
{
    memset(lev,0,4*T+4),q[h=t=lev[S]=1]=S; int i,u,v;
    while (h<=t) for (i=head[u=q[h++]]; i; i=nx[i])
	if (!lev[v=to[i]]&&cap[i]) lev[v]=lev[u]+1,q[++t]=v;
    return lev[T];
}

il int dfs(int u,int f)
{
    if (u==T) return f; int v,z,res=0;
    for (int &i=it[u]; i; i=nx[i])
	if (cap[i]&&lev[v=to[i]]==lev[u]+1&&(z=dfs(v,min(cap[i],f-res))))
	{
	    cap[i]-=z,cap[i^1]+=z,res+=z;
	    if (res==f) break;
	}
    return res;
}

il int dinic()
{
    int f,res=0;
    while (bfs())
    {
        memcpy(it,head,4*T+4);
        while (f=dfs(S,1e9)) res+=f;
    }
    return res;
}

int main()
{
    freopen("missile.in","r",stdin),freopen("missile.out","w",stdout);
	
    scanf("%d",&n),S=n+n+1,T=S+1; int i,j;
    for (i=1; i<=n; i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
    sort(p+1,p+n+1,cmp);

    for (i=1; i<=n; i++)
    {
	f[i]=1,ins(S,i,1),ins(i+n,T,1);
	for (j=1; j<i; j++)
	    if (p[j].x<p[i].x&&p[j].y<p[i].y&&p[j].z<p[i].z) f[i]=max(f[i],f[j]+1),ins(j,i+n,1);
	    ans=max(ans,f[i]);
    }
    printf("%d\n%d",ans,n-dinic());
	
    return 0;
}

Day7

T1 abc

简要题意：共有 $n$ 组询问，每次给定一个三个顶点都在格点上的三角形，求这个三角形的边界加内部共有多少个格点。

我们发现直角边平行于坐标轴的直角三角形与边平行于坐标轴的矩形内部的格点数都十分好算，那么我们使用割补法将其变成若干个矩形和直角三角形的和差，就可以计算了。

Code：

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define il inline
#define int long long
using namespace std;

int tt,ax,ay,bx,by,cx,cy,ans;

il int gcd(int a,int b){return b?gcd(b,a%b):a;}

il int cal(int x,int y)
{
    x=abs(x),y=abs(y);
    if (!x||!y) return 0;
    return ((x+1ll)*(y+1ll)-gcd(x,y)-1ll)/2ll;
}

il int check(int x,int y,int z){return (y-x)*(z-x)<0;}

signed main()
{
    freopen("abc.in","r",stdin),freopen("abc.out","w",stdout);
	
    scanf("%lld",&tt); int X1,Y1,X2,Y2;
    while (tt--)
    {
        scanf("%lld%lld%lld%lld%lld%lld",&ax,&ay,&bx,&by,&cx,&cy);
        ans=(max(ax,max(bx,cx))-min(ax,min(bx,cx))+1ll)*(max(ay,max(by,cy))-min(ay,min(by,cy))+1ll)-cal(ax-bx,ay-by)-cal(ax-cx,ay-cy)-cal(bx-cx,by-cy);
        if (check(ax,bx,cx)&&check(ay,by,cy)) ans-=min(abs((cx-ax)*(ay-by)),abs((ax-bx)*(cy-ay)));
        if (check(bx,ax,cx)&&check(by,ay,cy)) ans-=min(abs((cx-bx)*(by-ay)),abs((bx-ax)*(cy-by)));
        if (check(cx,bx,ax)&&check(cy,by,ay)) ans-=min(abs((cx-ax)*(cy-by)),abs((cx-bx)*(cy-ay)));
        printf("%lld\n",ans);
    }

    return 0;
}

T2 file

简要题意：求一条从圆上出发，经过折射 / 反射后最终沿 $x$ 轴正方向射到原点的光路。

考虑到光路可逆，问题转化为求一条从原点出发沿 $x$ 轴正方向射到圆上的光路。

代码没写。

T3 see

简要题意：有 $n$ 条形如 $y=kx+m$ 的直线，求可以从 $y$ 正负无穷远处看到的（只看到一个点的不算）直线的编号和。$n\le 10^5$，$|k|,|m|\le 10^9$。

将直线 $y=kx+m$ 映射到点 $(k,m)$ 上，那么可以被看见的直线就是这些映射过去的点形成的凸包。这十分显然。

于是直接求凸包即可，时间复杂度为 $O(n\log{n})$，空间复杂度为 $O(n)$。

Code：

#include <stdio.h>
#include <algorithm>
#define il inline
#define int long long
using namespace std;
const int N=1e5+5;

int n,ans,t;
struct vec{int x,y,id;}v[N],s[N];
il vec operator - (vec a,vec b){return (vec){a.x-b.x,a.y-b.y};}
il int operator & (vec a,vec b){return a.x*b.y-a.y*b.x;}
il bool operator < (vec a,vec b){return a.x==b.x?a.y<b.y:a.x<b.x;}

il void convex()
{
    sort(v+1,v+n+1); int i;
    for (i=1; i<=n; s[++t]=v[i++]) for ( ; t>1&&((s[t]-s[t-1])&(v[i]-s[t]))<=0; t--);
    for (i=1; i<=t; i++) ans+=s[i].id;
    for (i=1,t=0; i<=n; s[++t]=v[i++]) for ( ; t>1&&((s[t]-s[t-1])&(v[i]-s[t]))>=0; t--);
    for (i=2; i<t; i++) ans+=s[i].id;
}

signed main()
{
    freopen("see.in","r",stdin),freopen("see.out","w",stdout);
	
    scanf("%lld",&n); int i;
    for (i=1; i<=n; i++) scanf("%lld%lld",&v[i].x,&v[i].y),v[i].id=i;
	
    convex(),printf("%lld",ans);
  	
    return 0;
}

Day8

T1 split

简要题意：有 $n$ 堆石子，每堆石子有 $x_i$ 个。两个人玩组合游戏，每次行动可以在以下两种操作中选择一种进行，无法进行操作的玩家就失败了。

1. 选择一堆非空石子，拿走一个。
2. 选择一堆石子数为偶数的非空石子堆，假设石子数为 $2x$，那么拿走这堆石子，然后增加 $K$ 堆石子数为 $x$ 的石子堆。

问先还是后手获胜，$T$ 组数据。

$1\leq T\leq10,1\leq n\leq50000,1\leq K,x_i\leq10^9$。

若 $K$ 是偶数，那么转移到的状态一定是 $0$。而 $SG_1=1,SG_2=2$，其他奇数的都是 $0$，偶数的都是 $1$。

若 $K$ 是奇数，可以发现除了前几位以外，奇数位置的 $SG$ 值都是 $0$。我们可以暴力 $O(\log)$ 计算。

于是暴力求 $SG$ 函数算出 Nim 积即可，时间复杂度为 $O(Tn\log)$，空间复杂度为 $O(1)$。

#include <bits/stdc++.h>
#define il inline

int tt,n,m;

il int SG(int x)
{
    int a,b;
    if (m&1^1) return x<2?1:(x<3?2:x&1^1);
    else
    {
        if (x==1||x==3) return 1; if (x&1) return 0;
        return a=SG(x-1),b=SG(x>>1),a&&b?0:(a==1||b==1?2:1);
    }
    return 0;
}

int main()
{
	freopen("split.in","r",stdin),freopen("split.out","w",stdout);

	scanf("%d",&tt); int i,x,z;
    while(tt--)
    {
        scanf("%d%d",&n,&m),z=0;
        for (i=1; i<=n; i++) scanf("%d",&x),z^=SG(x);

        puts(z?"Alice":"Bob");
    }
	
	return 0;
}

T2 atm

简要题意：一个人初始时有 $h$ 滴血，还有 $n$ 个敌人，打倒第 $i$ 个敌人会先扣 $a_i$ 滴血，再回复 $b_i$ 滴血。安排一个打倒敌人的顺序，使得血量在任何时候为正，无解输出 $-1$。

把所有敌人分为回血大于扣血的和扣血大于回血的这两类。

对于前一类，这十分好处理，显然优先打扣血少的。

对于后一类，我们发现，若有解，则最终血量是定值，设其为 $x$。我们再考虑，如果有解，那么整个过程反过来也是有解的，那么我们将这一类回扣血是对调，然后同前一类做一遍贪心即可。

时间复杂度为 $O(n\log{n})$，空间复杂度为 $O(n)$。

Code：

#include <bits/stdc++.h>
#define il inline

int n,h,p;
struct node{int id,a,b;};
std::vector<node> v1,v2;

il bool cmp1(node a,node b){return a.a<b.a;}

il bool cmp2(node a,node b){return a.b<b.b;}

int main()
{
    freopen("atm.in","r",stdin),freopen("atm.out","w",stdout);
	
    scanf("%d%d",&n,&h),p=h; int i,a,b; node l;
    for (i=1; i<=n; i++)
    {
        scanf("%d%d",&a,&b),p+=b-a,l=(node){i,a,b};
        if (a<b) v1.push_back(l);
        else v2.push_back(l);
    }
    if (p<1) return 0*puts("-1");
    std::sort(v1.begin(),v1.end(),cmp1),std::sort(v2.begin(),v2.end(),cmp2);
	
    for (auto x:v1){h-=x.a; if  (h<1) return 0*puts("-1"); h+=x.b;}
    for (auto x:v2){p-=x.b; if  (p<1) return 0*puts("-1"); p+=x.a;}
    for (auto x:v1) printf("%d ",x.id);
    for (i=v2.size()-1; ~i; i--) printf("%d ",v2[i].id);
	
    return 0;
}

Day9

T1 transfer

简要题意：有一个 $n$ 个点 $m$ 条边的无向图，每条边有一个颜色，走过一条边需要花费 $1$ 的代价，但是连续走过颜色相同的边总共只需要花费 $1$ 的代价，求从 $1$ 到 $n$ 的最小代价。$2\le n\le 10^5$，$1\le m\le 2\times 10^5$。

考虑分层图，对于每一种颜色，我们都建一层图 $G_c$，原图 $G$ 的边 $(u,v,c)$ 映射到分层图中的 $(u,u_c,1),(v,v_c,0),(v,v_c,1)$，这样分层图中 $1\sim n$ 的最短路就是原图中 $1\sim n$ 的最短路的两倍。而分层图的点数和边数和原图都是同阶的，所以直接在上面跑最短路即可，空间复杂度为 $O(n+m)$，时间复杂度取决于使用的最短路算法，本人使用 bfs。

Code：

#include <stdio.h>
#include <string.h>
#include <unordered_map>
#define il inline
using namespace std;
const int N=5e5+5,M=1.5e6,F=0X3f3f3f;

int n,m,cnt,dis[N],q[M],h,t;
int to[M],nx[M],wt[M],hd[N],sze;
unordered_map<int,int> o[N];

il int id(int x,int c){return o[x][c]?o[x][c]:o[x][c]=++cnt;}

il void add(int u,int v,int w){to[++sze]=v,nx[sze]=hd[u],wt[sze]=w,hd[u]=sze;}

il void bfs()
{
    memset(dis,F,4*cnt+4),dis[q[h=t=1]=1]=0; int i,u,v;
    while (h<=t) for (i=hd[u=q[h++]]; i; i=nx[i])
	if (dis[v=to[i]]>dis[u]+wt[i]) dis[v]=dis[u]+wt[i],q[++t]=v;
}

int main()
{
    freopen("transfer.in","r",stdin),freopen("transfer.out","w",stdout);
	
    scanf("%d%d",&n,&m),cnt=n; int u,v,c,x,y;
    while (m--) scanf("%d%d%d",&u,&v,&c),x=id(u,c),y=id(v,c),
	add(u,x,1),add(x,u,1),add(v,y,1),add(y,v,1),add(x,y,0),add(y,x,0); 
	
    bfs(),printf("%d",dis[n]==F?-1:dis[n]/2);
	
    return 0;
}

T3 number

简要题意：有 $n$ 个数 $p_{1\sim n}$，求有多少种排列方式，使得这些数字顺次拼接起来得到的数字的是 $11$ 的倍数，答案对 $998,\,244,\,353$ 取模，多组数据。$1\le \sum{n},T\le 2000$，$1\le a_i\le 10^9$。

注意到 $11\equiv -1(\bmod 11)$，所以 $10^k\equiv \pm 1$。而在一个数 $x$ 前面加上另一个数 $y$ 得到的数字是 $y\times10^k+x\equiv \pm 1\times y+x(\bmod 11)$，而是乘上 $1$ 还是 $-1$ 则属由 $x$ 的位数来决定的。综合前面两个结论，我们可以得出，每个数对最后模 $11$ 意义下的贡献是它本身或者它的相反数。我们设对应 $1$ 的序列为 $a_{1\sim A}$，对应 $-1$ 的序列为 $b_{1\sim B}$。

我们又发现，对应 $-1$ 会将原数划分为若干个段，相邻两端的贡献正负性不同。于是我们考虑先将 $-1$ 填进去，因为这样可以让后面求解是更方便的知道这个数贡献的正负性。

考虑一个 DP，设 $g_{i,j,k}$ 表示考虑了前 $i$ 个对应 $-1$ 的数，其中有 $j$ 个最终的贡献为 $-1$，现在和为 $k$ 的方案数。那么先有 $g_{0,0,0}=\left(\left\lfloor \frac{B}{2}\right\rfloor\right)!+\left(\left\lceil \frac{B}{2}\right\rceil\right)!$。

而转移分两类：

• 若 $i-j\le \left\lceil \frac{B}{2}\right\rceil$，则有 $g_{i,j,(k-b_i)\bmod 11}\gets_{+} g_{i-1,j,k}$；
• 若 $j>0$，则有 $g_{i,j,(k+b_i)\bmod 11}\gets_{+}g_{i-1,j-1,k}$。

填完 $-1$ 后还要填剩下的，于是再设一个 DP 数组 $f_{i,j,k}$ 表示考虑到了前 $i$ 个对应 $1$ 的数，其中有 $j$ 个最终的贡献为 $-1$，现在和为 $k$ 的方案数，转移同之前类似。

时空复杂度均为 $O(11n^2)$。

Code：

#include <bits/stdc++.h>
#define il inline
#define ll long long
const int N=2005,P=998244353;

int tt,n,A,B,ans,a[N],b[N],fac[N],f[N][N][11],g[N][N][11];

int main()
{
    freopen("number.in","r",stdin),freopen("number.out","w",stdout);
	
    scanf("%d",&tt); int i,j,k,x;
    for (i=fac[0]=1; i<N; i++) fac[i]=(ll)fac[i-1]*i%P;
	
    while (tt--)
    {
        scanf("%d",&n),ans=A=B=0;
        for (i=1; i<=n; i++)
        {
            scanf("%d",&x);
            for (k=x,j=1; k; k/=10) j++;
            (j&1?a[++A]:b[++B])=x%11;
	}
	for (i=0; i<=A; i++) for (j=0; j<=A; j++) for (k=0; k<11; k++) f[i][j][k]=0;
	for (i=0; i<=B; i++) for (j=0; j<=B; j++) for (k=0; k<11; k++) g[i][j][k]=0;
		
	g[0][0][0]=(ll)fac[B/2]*fac[B+1>>1]%P;
	for (i=1; i<=B; i++) for (j=0; j<=i&j+j<=B; j++) for (k=0; k<11; k++)
	{
	    if (i-j<=B+1>>1) g[i][j][(k-b[i]+11)%11]=(g[i][j][(k-b[i]+11)%11]+g[i-1][j][k])%P;
	    if (j) g[i][j][(k+b[i])%11]=(g[i][j][(k+b[i])%11]+g[i-1][j-1][k])%P;
	}
	for (k=0; k<11; k++) f[0][0][k]=g[B][B/2][k];
	for (i=1; i<=A; i++) for (j=0; j<i; j++) for (k=0; k<11; k++)
	    f[i][j+1][(k+a[i])%11]=(f[i][j+1][(k+a[i])%11]+(ll)f[i-1][j][k]*(B/2+j+1))%P,f[i][j][(k-a[i]+11)%11]=(f[i][j][(k-a[i]+11)%11]+(ll)f[i-1][j][k]*((B+1)/2-1+i-j))%P;
	for (j=0; j<=A; j++) ans=(ans+f[A][j][0])%P;
	printf("%d\n",ans);
    }
	
    return 0;
}